<!doctype html><html lang=en-us><head><meta charset=utf-8><meta name=viewport content="width=device-width,initial-scale=1"><meta name=description content="Codesim A similarity measurer on two programming assignments on Online Judge.
 GitHub  The code similarity measuring algorithm originates from
 Jiang Y, Xu C. Needle: Detecting code plagiarism on student submissions[C]//Proceedings of ACM Turing Celebration Conference-China. 2018: 27-32.
 Goals  From PA1&amp;rsquo;s goals and Needle&amp;rsquo;s paper
 We want to measure similarity between two programming assignments $A$ and $B$ on Online Judge to find possible plagiarism. We assume that each input program is a single-file C++ program that can be compiled by g++ -std=c++17 -pedantic."><title>Codesim</title><link rel=canonical href=https://stardustdl.gitee.io/posts/projects/codesim/><link rel=stylesheet href=/scss/style.min.css><meta property="og:title" content="Codesim"><meta property="og:description" content="Codesim A similarity measurer on two programming assignments on Online Judge.
 GitHub  The code similarity measuring algorithm originates from
 Jiang Y, Xu C. Needle: Detecting code plagiarism on student submissions[C]//Proceedings of ACM Turing Celebration Conference-China. 2018: 27-32.
 Goals  From PA1&amp;rsquo;s goals and Needle&amp;rsquo;s paper
 We want to measure similarity between two programming assignments $A$ and $B$ on Online Judge to find possible plagiarism. We assume that each input program is a single-file C++ program that can be compiled by g++ -std=c++17 -pedantic."><meta property="og:url" content="https://stardustdl.gitee.io/posts/projects/codesim/"><meta property="og:site_name" content="StardustDL's Blog"><meta property="og:type" content="article"><meta property="article:section" content="Posts"><meta property="article:published_time" content="2021-12-21T14:14:53+08:00"><meta property="article:modified_time" content="2021-12-21T14:14:53+08:00"><meta name=twitter:title content="Codesim"><meta name=twitter:description content="Codesim A similarity measurer on two programming assignments on Online Judge.
 GitHub  The code similarity measuring algorithm originates from
 Jiang Y, Xu C. Needle: Detecting code plagiarism on student submissions[C]//Proceedings of ACM Turing Celebration Conference-China. 2018: 27-32.
 Goals  From PA1&amp;rsquo;s goals and Needle&amp;rsquo;s paper
 We want to measure similarity between two programming assignments $A$ and $B$ on Online Judge to find possible plagiarism. We assume that each input program is a single-file C++ program that can be compiled by g++ -std=c++17 -pedantic."><link rel="shortcut icon" href=/favicon.png><script type=application/javascript>var doNotTrack=!1;doNotTrack||(function(a,e,f,g,b,c,d){a.GoogleAnalyticsObject=b,a[b]=a[b]||function(){(a[b].q=a[b].q||[]).push(arguments)},a[b].l=1*new Date,c=e.createElement(f),d=e.getElementsByTagName(f)[0],c.async=1,c.src=g,d.parentNode.insertBefore(c,d)}(window,document,'script','https://www.google-analytics.com/analytics.js','ga'),ga('create','UA-111573521-1','auto'),ga('send','pageview'))</script></head><body class="article-page has-toc"><script>(function(){const a='StackColorScheme';localStorage.getItem(a)||localStorage.setItem(a,"auto")})()</script><script>(function(){const b='StackColorScheme',a=localStorage.getItem(b),c=window.matchMedia('(prefers-color-scheme: dark)').matches===!0;a=='dark'||a==='auto'&&c?document.documentElement.dataset.scheme='dark':document.documentElement.dataset.scheme='light'})()</script><div class="container main-container flex
extended"><div id=article-toolbar><a href=/ class=back-home><svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-chevron-left" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentcolor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z"/><polyline points="15 6 9 12 15 18"/></svg><span>Back</span></a></div><main class="main full-width"><article class=main-article><header class=article-header><div class=article-details><header class=article-category><a href=/categories/projects/>Projects</a></header><h2 class=article-title><a href=/posts/projects/codesim/>Codesim</a></h2><footer class=article-time><div><svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-calendar-time" width="56" height="56" viewBox="0 0 24 24" stroke-width="2" stroke="currentcolor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z"/><path d="M11.795 21H5a2 2 0 01-2-2V7a2 2 0 012-2h12a2 2 0 012 2v4"/><circle cx="18" cy="18" r="4"/><path d="M15 3v4"/><path d="M7 3v4"/><path d="M3 11h16"/><path d="M18 16.496V18l1 1"/></svg><time class=article-time--published>Dec 21, 2021</time></div><div><svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-clock" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentcolor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z"/><circle cx="12" cy="12" r="9"/><polyline points="12 7 12 12 15 15"/></svg><time class=article-time--reading>3 minute read</time></div></footer></div></header><section class=article-content><h1 id=codesim>Codesim</h1><p>A similarity measurer on two programming assignments on Online Judge.</p><ul><li><a class=link href=https://github.com/StardustDL/codesim target=_blank rel=noopener>GitHub</a></li></ul><p>The code similarity measuring algorithm originates from</p><blockquote><p>Jiang Y, Xu C. Needle: Detecting code plagiarism on student submissions[C]//Proceedings of ACM Turing Celebration Conference-China. 2018: 27-32.</p></blockquote><h2 id=goals>Goals</h2><blockquote><p>From PA1&rsquo;s goals and Needle&rsquo;s paper</p></blockquote><p>We want to measure similarity between two programming assignments $A$ and $B$ on Online Judge to find possible plagiarism.
We assume that each input program is a single-file C++ program that can be compiled by <code>g++ -std=c++17 -pedantic</code>.</p><h2 id=preprocessing>Preprocessing</h2><p>The compiling and optimization removes comments, macros and unnessesary code, ignores local variable names and code format.
Many redundant changes will have zero or minor impacts after compiler optimization and it is a good way to normalize a program.
To decrease obfuscation changes' impacts further, we use opcode sequence as a function&rsquo;s figureprint and ignore operands.</p><p>A program is a set of functions, and a function is a sequence of opcodes.</p><p>We first compile the input code by <code>g++</code> with <code>-O2</code> optimization level.
To keep the generated object file clean, we use <code>-c</code> option to prevent generating initializing function.</p><p>Then we use <code>objdump</code> to disassembly object files, collect and filter (ignore <code>nop</code> and unrecogized opcodes) opcode sequence.</p><h2 id=similarity>Similarity</h2><p>One common kind of obfuscation changes is splitting one function into many functions.
To address this, we calculate inter-function similarity (as same as the program similarity) with intra-function similarity.
The main idea is mapping each instruction in program $A$ to the most similar instruction in program $B$.</p><h3 id=intra-function-similarity>Intra-function Similarity</h3><p>Intra-function similarity models the similarity of a instruction in a specific function context.</p><p>Let $f\in A$ be a function from program $A$, and $g$ be a function from program $B$.
If $f$ can be extended to $g$, then there may be a code copy case.
We use longest common subsequence (LCS) to calculate the cost to extend $f$ to $g$.
To preserve integrity of $f$ during extending, we calculate the longest LCS in a fixed window size $\omega=\frac{3}{2}|f|$.</p><p>$$\sigma(f,g)=\max_{k\in\{1,2,\dots,|g|\}}\text{LCS}(f,g[k:k+\omega])$$</p><p>Formally, the intra-function similarity between $f$ and $g$ is defined as</p><p>$$\rho(f,g)=\frac{\max\{\sigma(f_i,g_j),\sigma(g_j,f_i)\}}{\min\{|f_i|,|g_j|\}}$$</p><p>For efficiency, we use the following strategies</p><ul><li>Use integer for opcode to speed up comparison.</li><li>Calculate $\sigma(f,g)$ by the following formula.</li></ul><p>$$\sigma(f,g)=\begin{cases}
\text{LCS}(f,g) & \omega>=|g| \\<br>\max_{k\in\{1,2,\dots,|g|-\omega\}}\text{LCS}(f,g[k:k+\omega]) & \text{otherwise}
\end{cases}$$</p><h3 id=inter-function-similarity>Inter-function Similarity</h3><p>We models the mapping problem by a weighted flow network graph $G=(V,E,c:E\rightarrow \mathbb{N},w:E\rightarrow \mathbb{R})$.</p><p>Let $n=|A|,m=|B|,i\in[n], j\in [m],f_i\in A,g_j\in B$.</p><p>$$\begin{aligned}
V&=\{s,t\}\cup\{l_i\}\cup\{r_j\}\\<br>E&=\{(s,l_i)\}\cup\{(r_j,t)\}\cup \{(l_i,r_j)\}\\<br>c(s,l_i)&=|f_i|,w(s,l_i)=0\\<br>c(r_j,t)&=|g_j|,w(r_j,t)=0\\<br>c(l_i,r_j)&=\sigma(f_i,g_j)\\<br>w(l_i,r_j)&=\text{sigmoid}'(\rho(f,g))
\end{aligned}$$</p><p>We use sigmoid function&rsquo;s center part, $\text{sigmoid}'(x)=\text{sigmoid}(\alpha x+\beta)$, with constants $\alpha=2,\beta=-1/2$ to normalize $\rho(f,g)$.</p><p>Then the unnormalized inter-function similarity from $A$ to $B$ is defined as</p><p>$$
\rho'(A\rightarrow B)=\frac{\text{MaximumWeightFlow(G)}}{\sum_{i}|f_i|}
$$</p><p>Then normalize $\rho'(A\rightarrow B)$ onto $[0,1]$.</p><p>$$
\rho(A\rightarrow B)=\frac{\rho'(A\rightarrow B)}{\text{sigmoid}'(1)}
$$</p><p>Finally the inter-function similarity between $A$ and $B$ is defined as the average of the two directions.</p><p>$$
\rho(A,B)=\frac{\rho(A\rightarrow B)+\rho(B\rightarrow A)}{2}
$$</p><p>For efficiency, we use the following strategies</p><ul><li>Calculate $\sigma(f_i,g_j)$ for all $(i,j)$ pairs parallel and cache the results.</li><li>Use integer $\lfloor \theta \cdot w(l_i,r_j) \rfloor$, in which $\theta=10000$, to replace the real number $w(l_i,r_j)$.</li></ul></section><footer class=article-footer><section class=article-copyright><svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-copyright" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentcolor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z"/><circle cx="12" cy="12" r="9"/><path d="M14.5 9a3.5 4 0 100 6"/></svg><span>Licensed under CC BY-NC-SA 4.0</span></section></footer><link rel=stylesheet href=https://cdn.jsdelivr.net/npm/katex@0.13.13/dist/katex.min.css integrity=sha384-RZU/ijkSsFbcmivfdRBQDtwuwVqK7GMOw6IMvKyeWL2K5UAlyp6WonmB8m7Jd0Hn crossorigin=anonymous><script src=https://cdn.jsdelivr.net/npm/katex@0.13.13/dist/katex.min.js integrity=sha384-pK1WpvzWVBQiP0/GjnvRxV4mOb0oxFuyRxJlk6vVw146n3egcN5C925NCP7a7BY8 crossorigin=anonymous defer></script><script src=https://cdn.jsdelivr.net/npm/katex@0.13.13/dist/contrib/auto-render.min.js integrity=sha384-vZTG03m+2yp6N6BNi5iM4rW4oIwk5DfcNdFfxkk9ZWpDriOkXX8voJBFrAO7MpVl crossorigin=anonymous defer></script><script>window.addEventListener("DOMContentLoaded",()=>{renderMathInElement(document.querySelector(`.article-content`),{delimiters:[{left:"$$",right:"$$",display:!0},{left:"$",right:"$",display:!1},{left:"\\(",right:"\\)",display:!1},{left:"\\[",right:"\\]",display:!0}]})})</script></article><aside class=related-contents--wrapper><h2 class=section-title>Related contents</h2><div class=related-contents><div class="flex article-list--tile"><article class=has-image><a href=/posts/projects/acblog-staticgen/><div class=article-image><img src=/posts/projects/acblog-staticgen/head.1953b2dd64e2e7e1cbeac076ef8398b4_hu9efe531bff7b440f821e48b9e03327e7_46403_250x150_fill_box_smart1_2.png width=250 height=150 loading=lazy alt="Featured image of post AcBlog 静态博客生成器使用说明" data-hash="md5-GVOy3WTi5+HL6sB274OYtA=="></div><div class=article-details><h2 class=article-title>AcBlog 静态博客生成器使用说明</h2></div></a></article><article class=has-image><a href=/posts/projects/images-dev/><div class=article-image><img src=/posts/projects/images-dev/head.2b9e292191d99c769569191d6d994d0a_hu305c74f0c0f0b5e138f098c149d6d1b0_54241_250x150_fill_box_smart1_2.png width=250 height=150 loading=lazy alt="Featured image of post ImagingS 开发笔记" data-hash="md5-K54pIZHZnHaVaRkdbZlNCg=="></div><div class=article-details><h2 class=article-title>ImagingS 开发笔记</h2></div></a></article></div></div></aside><script src=https://utteranc.es/client.js repo=StardustDL/stardustdl.github.io issue-term=pathname label=comment crossorigin=anonymous async></script><style>.utterances{max-width:unset}</style><script>function setUtterancesTheme(b){let a=document.querySelector('.utterances iframe');a&&a.contentWindow.postMessage({type:'set-theme',theme:`github-${b}`},'https://utteranc.es')}addEventListener('message',a=>{if(a.origin!=='https://utteranc.es')return;setUtterancesTheme(document.documentElement.dataset.scheme)}),window.addEventListener('onColorSchemeChange',a=>{setUtterancesTheme(a.detail)})</script><footer class=site-footer><section class=copyright>&copy;
2017 -
2021 StardustDL's Blog</section><section class=powerby><a style=color:gray href=http://www.beian.miit.gov.cn>冀ICP备19021004号</a><br>Built with <a href=https://gohugo.io/ target=_blank rel=noopener>Hugo</a><br>Theme <b><a href=https://github.com/CaiJimmy/hugo-theme-stack target=_blank rel=noopener data-version=3.5.0>Stack</a></b> designed by <a href=https://jimmycai.com target=_blank rel=noopener>Jimmy</a></section></footer><div class=pswp tabindex=-1 role=dialog aria-hidden=true><div class=pswp__bg></div><div class=pswp__scroll-wrap><div class=pswp__container><div class=pswp__item></div><div class=pswp__item></div><div class=pswp__item></div></div><div class="pswp__ui pswp__ui--hidden"><div class=pswp__top-bar><div class=pswp__counter></div><button class="pswp__button pswp__button--close" title="Close (Esc)"></button>
<button class="pswp__button pswp__button--share" title=Share></button>
<button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>
<button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button><div class=pswp__preloader><div class=pswp__preloader__icn><div class=pswp__preloader__cut><div class=pswp__preloader__donut></div></div></div></div></div><div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap"><div class=pswp__share-tooltip></div></div><button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)"></button>
<button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)"></button><div class=pswp__caption><div class=pswp__caption__center></div></div></div></div></div><script src=https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.js integrity="sha256-ePwmChbbvXbsO02lbM3HoHbSHTHFAeChekF1xKJdleo=" crossorigin=anonymous defer></script><script src=https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe-ui-default.min.js integrity="sha256-UKkzOn/w1mBxRmLLGrSeyB4e1xbrp4xylgAWb3M42pU=" crossorigin=anonymous defer></script><link rel=stylesheet href=https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/default-skin/default-skin.css integrity="sha256-c0uckgykQ9v5k+IqViZOZKc47Jn7KQil4/MP3ySA3F8=" crossorigin=anonymous><link rel=stylesheet href=https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.css integrity="sha256-SBLU4vv6CA6lHsZ1XyTdhyjJxCjPif/TRkjnsyGAGnE=" crossorigin=anonymous></main><aside class="sidebar right-sidebar sticky"><section class="widget archives"><div class=widget-icon><svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-hash" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentcolor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z"/><line x1="5" y1="9" x2="19" y2="9"/><line x1="5" y1="15" x2="19" y2="15"/><line x1="11" y1="4" x2="7" y2="20"/><line x1="17" y1="4" x2="13" y2="20"/></svg></div><h2 class="widget-title section-title">Table of contents</h2><div class=widget--toc><nav id=TableOfContents><ol><li><a href=#codesim>Codesim</a><ol><li><a href=#goals>Goals</a></li><li><a href=#preprocessing>Preprocessing</a></li><li><a href=#similarity>Similarity</a><ol><li><a href=#intra-function-similarity>Intra-function Similarity</a></li><li><a href=#inter-function-similarity>Inter-function Similarity</a></li></ol></li></ol></li></ol></nav></div></section></aside></div><script src=https://cdn.jsdelivr.net/npm/node-vibrant@3.1.5/dist/vibrant.min.js integrity="sha256-5NovOZc4iwiAWTYIFiIM7DxKUXKWvpVEuMEPLzcm5/g=" crossorigin=anonymous defer></script><script type=text/javascript src=/ts/main.js defer></script><script>(function(){const a=document.createElement('link');a.href="https://fonts.googleapis.com/css2?family=Lato:wght@300;400;700&display=swap",a.type="text/css",a.rel="stylesheet",document.head.appendChild(a)})()</script></body></html>